class Solution:
    def kSum(self, nums, k, beg, target):
        """
        :type nums: []
        """
        ret = []
        if k == 1:
            used = {}
            for i in range(beg, len(nums)):
                if nums[i] == target and not used.has_key(nums[i]):
                    ret.append([nums[i]])
                    used[nums[i]] = 1
        else:
            used = {}
            for i in range(beg, len(nums)):
                if used.has_key(nums[i]):
                    continue
                used[nums[i]] = 1
                tmp = self.kSum(nums, k-1, i+1, target-nums[i])
                for j, tmplist in enumerate(tmp):
                    tmplist.insert(0, nums[i])
                    ret.append(tmplist)
        return ret

    # @param {integer[]} nums
    # @return {integer[][]}
    def threeSum(self, nums):
        """
        :type nums: []
        """
        if len(nums) < 3:
            return []
        nums = sorted(nums)
        return self.kSum(nums, 3, 0, 0)



